package day05

import "math"

// day05
//
// 377. 组合总和 Ⅳ
//
// https://leetcode.cn/problems/combination-sum-iv/
//
// ```go
func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1
	for j := 0; j <= target; j++ {
		for i := 0; i < len(nums); i++ {
			if j >= nums[i] {
				dp[j] += dp[j-nums[i]]
			}
		}
	}
	return dp[target]
}

//```

// 322. 零钱兑换
//
// https://leetcode.cn/problems/coin-change/
//
// ```go
func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = math.MaxInt32
	}
	dp[0] = 0
	for i := 0; i < len(coins); i++ {
		for j := coins[i]; j <= amount; j++ {
			dp[j] = min(dp[j], dp[j-coins[i]]+1)
		}
	}
	if dp[amount] == math.MaxInt32 {
		return -1
	}
	return dp[amount]
}

//```

// 279. 完全平方数
//
// https://leetcode.cn/problems/perfect-squares/
//
// ```go
func numSquares(n int) int {
	nums := make([]int, n)
	for i := range nums {
		nums[i] = (i + 1) * (i + 1)
	}
	dp := make([]int, n+1)
	for i := range dp {
		dp[i] = math.MaxInt32
	}
	dp[0] = 0
	for i := 0; i < len(nums); i++ {
		for j := nums[i]; j <= n; j++ {
			dp[j] = min(dp[j], dp[j-nums[i]]+1)
		}
	}
	return dp[n]
}

//```
